public class Text8 {
    //76.最小覆盖子串
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();

        int[] hash1 = new int[128];
        int kinds = 0;
        for(char a : tt)
            if(hash1[a]++ == 0) kinds++;

        int[] hash2 = new int[128];

        int count = 0, min = -1, begin = -1;
        for(int left = 0, right = 0; right < ss.length; right++){
            char in = ss[right];
            if(++hash2[in]==hash1[in])
                count++;

            while(kinds == count){

                if(right - left + 1 < min || min == -1){
                    min = right - left + 1;
                    begin = left;
                }

                char out = ss[left++];
                if(hash2[out]-- == hash1[out])
                    count--;
            }
        }

        if(begin == -1) return new String();
        else return s.substring(begin,begin + min);
    }
}
